package main

import "fmt"

func main() {
	fmt.Println(numTrees(19))
}

var dp = map[int]int{0: 1}

func numTrees(n int) int {
	if dp[n] != 0 {
		return dp[n]
	}
	sum := 0
	for i := 1; i <= n; i++ {
		sum += numTrees(i-1) * numTrees(n-i)
	}
	dp[n] = sum
	return sum
}
